package com.hh.hot100;

/**
 * @Author hanghao
 * @Date 2023/6/27 16:13
 * @Version 1.0
 * middle
 * 轮转数组
 * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 */

public class No189 {
    public static void rotate(int[] nums, int k) {
        k %= nums.length;
        //空间复杂度为O(1)
        reverse(nums,0,nums.length - 1);
        reverse(nums,0,k - 1);
        reverse(nums,k,nums.length - 1);


//        //这种方法的空间复杂度为O(n)  题目要求空间复杂度为O(1)
//        LinkedList<Integer> list = new LinkedList<>();
//        for (int num : nums) {
//            list.add(num);
//        }
//        int len = list.size();
//        int length = nums.length;
//        int num = k % length;
//        while (num > 0) {
//            Integer removed = list.remove(length - 1);
//            list.add(0,removed);
//            num--;
//        }
//        for (int i = 0; i < nums.length; i++) {
//            nums[i] = list.get(i);
//        }
    }

    private static void reverse(int[] nums, int i, int length) {
        int left = i;
        int right = length;
        while(left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] nums =new int[]{1,2,3,4,5,6,7};
        int k = 3;
        rotate(nums,k);
        for (int num : nums) {
            System.out.println(num + "");
        }
    }
}
